package leetcode101.dynamic_planning;

/**
 * @author Synhard
 * @version 1.0
 * @Class Code31
 * @Description TODO
 * @tel 13001321080
 * @email 823436512@qq.com
 * @date 2021-04-26 9:25
 */
public class Code31 {

    public static void main(String[] args) {
        int[] arr = new int[]{
                1793, 140, 1187, 199, 722, 1067, 817, 324, 1499, 805, 1910, 1811,
                1365, 509, 1255, 1393, 1098, 594, 309, 518, 218, 393, 1270, 1788,
                1710, 1858, 1284, 1213, 888, 639, 467, 1404, 691, 1623, 1969, 129,
                52, 504, 559, 816, 1980, 1675, 1355, 1722, 1506, 1931, 464, 168,
                1845, 1321
        };
        int[] ans = theMostCharmingSequence(arr);
        System.out.println(ans[1]);
        System.out.println(ans[0]);
    }

    public static int[] theMostCharmingSequence(int[] arr) {
        int n = arr.length + 1;
        int[][] dp = new int[n][n];
        int[] nums = new int[n];
        int max = 0;
        int[] ans = new int[2];

        for (int i = 3; i < dp.length; i++) {
            for (int j = i - 1; j > 1; j--) {
                for (int k = j - 1; k > 0; k--) {
                    if (arr[i - 1] == arr[j - 1] * arr[k - 1] % 2021) {
                        dp[i][j] = Math.max(dp[i][j], dp[j][k] + 1);
                        nums[dp[i][j]]++;
                    }
                }
                max = Math.max(max, dp[i][j]);
            }
        }
        ans[0] = max + 2;
        ans[1] = nums[max];
        return ans;
    }
}
